from typing import *
from bisect import bisect_left


class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        cnt = Counter(power)
        keys = sorted(cnt.keys())
        f = [0] * len(keys)
        for i, v in enumerate(keys):
            k = bisect_left(keys, v - 2) - 1
            f[i] = max(cnt[v] * v + (0 if k < 0 else f[k]), f[i - 1])
        return f[-1]


class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        cnt = Counter(power)
        keys = sorted(cnt.keys())
        n = len(keys)
        f = [0] * n
        l = 0
        mx = 0
        for i, v in enumerate(keys):
            while l < i and keys[l] < v - 2:
                mx = max(mx, f[l])
                l += 1
            f[i] = max(f[i - 1], mx + cnt[v] * v)
        return f[-1]


s = Solution()
print(s.maximumTotalDamage(power=[7, 1, 6, 3]))
print(s.maximumTotalDamage(power=[7, 1, 6, 6]))
